package _linklist

import org.junit.Assert
import org.junit.Test

/**
 * 206. 反转链表
 * https://leetcode.cn/problems/reverse-linked-list/description/
 * https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html
 *
 * 输入：head = [1,2,3,4,5]
 * 输出：[5,4,3,2,1]
 *
 * 输入：head = [1,2]
 * 输出：[2,1]
 *
 * 输入：head = []
 * 输出：[]
 */
class leetcode_206 {

    @Test
    fun test_1() {
        val l1 = ListNode(1)
        val l2 = ListNode(2)
        val l3 = ListNode(3)
        l1.next = l2
        l2.next = l3
        val actual = reverseList(l1)
        val expect = "3,2,1,"
        Assert.assertEquals(actualString(actual), expect)
    }

    @Test
    fun test_2() {
        val l1 = ListNode(1)
        val l2 = ListNode(2)
        l1.next = l2
        val actual = reverseList(l1)
        val expect = "2,1,"
        Assert.assertEquals(actualString(actual), expect)
    }

    @Test
    fun test_3() {
        val actual = reverseList(null)
        val expect = ""
        Assert.assertEquals(actualString(actual), expect)
    }

    private fun actualString(list: ListNode?): String {
        var str: String = ""
        var p: ListNode? = list
        while (p != null) {
            str = str + p.`val` + ","
            p = p.next
        }
        return str
    }

    // 1  -> 2  -> 3 -> NULL
    // 第1次   NULL (prev)) || 1 current -> 2 next  -> 3 -> NULL
    // 第2次   NULL <- 1 (prev)) || 2 current  -> 3  next -> NULL
    // 第3次   NULL <- 1  <- 2 (prev) ) || 3  current -> next NULL
    // 第4次   NULL <- 1  <- 2 <-3 (prev) ) || current NULL
    //  =>  prev

    private fun reverseList(head: ListNode?): ListNode? {
        return reverseList1(head);
//        return reverseList2(head);
    }

    private fun reverseList1(head: ListNode?): ListNode? {
        // 双指针法
        // T - N
        // S - 1
        var prev: ListNode? = null
        var current: ListNode? = head
        var next: ListNode? = null

        while (current != null) {
            next = current?.next
            current?.next = prev
            prev = current
            current = next
        }
        return prev
    }

    private class ListNode(var `val`: Int) {
        var next: ListNode? = null
    }

    private fun reverseList2(head: ListNode?): ListNode? {
        // 递归方法
        // T - N
        // S - N
        return reverse(head, null)
    }

    private fun reverse(current: ListNode?, prev: ListNode?): ListNode? {
        if (current == null) {
            return prev
        }
        val next: ListNode? = current.next;
        current?.next = prev
        return reverse(next, current)
    }
}